SP694 DISUBSTR - Distinct Substrings

这道题用后缀自动机可以暴力解决。

建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 ， 我们就可以在 $\text{DAWG}$ 上 $dp$ 。 $dp[u]$表示包含转移$u$的子串数量，很容易列出转移式：

$dp[u]=\sum_{v \in son[u]} dp[v]$

注意虽然是一个$\text{DAG}$，但是我们并不需要把图建出，只需要用拓扑序$dp$就可以了。

注意，此题不一定是小写字母！！！

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 1000 , MAXK = 256;
struct Suffix_Automaton {
	int Root , Size , Last , Maxlen[ 2 * MAXN + 5 ]; 
	int Trans[ 2 * MAXN + 5 ][ MAXK + 5 ] , Link[ 2 * MAXN + 5 ];
	long long dp[ 2 * MAXN + 5 ];
	
	Suffix_Automaton( ) { Root = Size = Last = 1; }
	
	void Copy( int u , int v ) {
		for( int i = 1 ; i <= MAXK ; i ++ )
			Trans[ u ][ i ] = Trans[ v ][ i ];
	}
	void Extend( int chr ) {
		int Newnode = ++ Size , u = Last;
		Maxlen[ Newnode ] = Maxlen[ u ] + 1;
		
		for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
			Trans[ u ][ chr ] = Newnode;
		
		if( !u ) Link[ Newnode ] = 1;
		else {
			int v = Trans[ u ][ chr ];
			
			if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
			else {
				int w = ++ Size;
				Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
				for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
				Link[ w ] = Link[ v ];
				Link[ v ] = Link[ Newnode ] = w;	
			}
		}
		Last = Newnode;
	}
	void Build( char *str ) {
		Root = Size = Last = 1;
		memset( Trans , 0 , sizeof( Trans ) );
		memset( Link , 0 , sizeof( Link ) );
		memset( dp , 0 , sizeof( dp ) ); 
		memset( tot , 0 , sizeof( tot ) ); 
		
		int len = strlen( str );
		for( int i = 0 ; i < len ; i ++ )
			Extend( str[ i ] );
		Sort( );
	}
	
	int tot[ 2 * MAXN + 5 ] , Topu[ 2 * MAXN + 5 ];
	void Sort( ) {
		for( int i = 1 ; i <= Size ; i ++ ) tot[ Maxlen[ i ] ] ++;
		for( int i = 1 ; i <= Size ; i ++ ) tot[ i ] += tot[ i - 1 ];
		for( int i = 1 ; i <= Size ; i ++ ) Topu[ tot[ Maxlen[ i ] ] -- ] = i; 
	} 
	
	long long Dp( ) {
		for( int i = Size ; i >= 1 ; i -- ) { //深度从大到小
			int u = Topu[ i ];
			dp[ u ] = ( u > 1 );
			for( int k = 1 ; k <= MAXK ; k ++ )
				if( Trans[ u ][ k ] ) dp[ u ] += dp[ Trans[ u ][ k ] ]; 
		}
		return dp[ Topu[ Root ] ]; //这里写成dp[ Root ]也没有问题，起点的拓扑序一定是最大的
	}
}SAM;

int t;
char str[ MAXN + 5 ];

int main( ) {
	scanf("%d",&t);
	while( t -- ) {
		scanf("%s", str );
		SAM.Build( str );
		printf("%lld\n", SAM.Dp( ) );
	}
	return 0;
}